{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Analyze User Website Visit Pattern"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mostVisitedPattern"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #用户网站访问行为分析"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个字符串数组&nbsp;<code>username</code>&nbsp;和&nbsp;<code>website</code>&nbsp;和一个整数数组&nbsp;<code>timestamp</code>&nbsp;。给定的数组长度相同，其中元组&nbsp;<code>[username[i], website[i], timestamp[i]]</code>&nbsp;表示用户&nbsp;<code>username[i]</code>&nbsp;在时间&nbsp;<code>timestamp[i]</code>&nbsp;访问了网站&nbsp;<code>website[i]</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>访问模式</strong> 是包含三个网站的列表(不一定是完全不同的)。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>[\"home\"， \"away\"， \"love\"]</code>， <code>[\"leetcode\"， \"love\"， \"leetcode\"]</code>，和 <code>[\"luffy\"， \"luffy\"， \"luffy\"]</code> 都是模式。</li>\n",
    "</ul>\n",
    "\n",
    "<p>一种&nbsp;<strong>访问</strong><strong>模式</strong> 的 <strong>得分</strong> 是访问该模式中所有网站的用户数量，这些网站在该模式中出现的顺序相同。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，如果模式是 <code>[“home”，“away”，“love”] </code>，那么分数就是用户数量 <code>x</code> , <code>x</code> 访问了 “<code>home”</code> ，然后访问了 <code>“away”</code> ，然后访问了 <code>“love” </code>。</li>\n",
    "\t<li>同样，如果模式是 <code>[\"leetcode\"， \"love\"， \"leetcode\"]</code> ，那么分数就是用户数量&nbsp;<code>x</code>&nbsp;，使得 <code>x</code> 访问了<code>\"leetcode\"</code>，然后访问了 <code>\"love\"</code> ，之后又访问了 <code>\"leetcode\"</code> 。</li>\n",
    "\t<li>另外，如果模式是 <code>[“luffy”，“luffy”，“luffy”]</code>&nbsp;，那么分数就是用户数量 <code>x</code> ，这样 <code>x</code> 就可以在不同的时间戳上访问 <code>“luffy”</code> 三次。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回<em> <strong>得分</strong> 最大的 <strong>访问</strong><strong>模式</strong></em> 。如果有多个访问模式具有相同的最大分数，则返回字典序最小的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>username = [\"joe\",\"joe\",\"joe\",\"james\",\"james\",\"james\",\"james\",\"mary\",\"mary\",\"mary\"], timestamp = [1,2,3,4,5,6,7,8,9,10], website = [\"home\",\"about\",\"career\",\"home\",\"cart\",\"maps\",\"home\",\"home\",\"about\",\"career\"]\n",
    "<strong>输出：</strong>[\"home\",\"about\",\"career\"]\n",
    "<strong>解释：</strong>本例中的元组是:\n",
    "[\"joe\",\"home\",1],[\"joe\",\"about\",2],[\"joe\",\"career\",3],[\"james\",\"home\",4],[\"james\",\"cart\",5],[\"james\",\"maps\",6],[\"james\",\"home\",7],[\"mary\",\"home\",8],[\"mary\",\"about\",9], and [\"mary\",\"career\",10].\n",
    "模式(\"home\", \"about\", \"career\") has score 2 (joe and mary).\n",
    "模式(\"home\", \"cart\", \"maps\") 的得分为 1 (james).\n",
    "模式 (\"home\", \"cart\", \"home\") 的得分为 1 (james).\n",
    "模式 (\"home\", \"maps\", \"home\") 的得分为 1 (james).\n",
    "模式 (\"cart\", \"maps\", \"home\") 的得分为 1 (james).\n",
    "模式 (\"home\", \"home\", \"home\") 的得分为 0(没有用户访问过home 3次)。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> username = [\"ua\",\"ua\",\"ua\",\"ub\",\"ub\",\"ub\"], timestamp = [1,2,3,4,5,6], website = [\"a\",\"b\",\"a\",\"a\",\"b\",\"c\"]\n",
    "<strong>输出:</strong> [\"a\",\"b\",\"a\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= username.length &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= username[i].length &lt;= 10</code></li>\n",
    "\t<li><code>timestamp.length == username.length</code></li>\n",
    "\t<li><code>1 &lt;= timestamp[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>website.length == username.length</code></li>\n",
    "\t<li><code>1 &lt;= website[i].length &lt;= 10</code></li>\n",
    "\t<li><code>username[i]</code> 和&nbsp;<code>website[i]</code>&nbsp;都只含小写字符</li>\n",
    "\t<li>它保证至少有一个用户访问了至少三个网站</li>\n",
    "\t<li>所有元组&nbsp;<code>[username[i]， timestamp[i]， website[i]</code>&nbsp;均<strong>&nbsp;不重复</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [analyze-user-website-visit-pattern](https://leetcode.cn/problems/analyze-user-website-visit-pattern/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [analyze-user-website-visit-pattern](https://leetcode.cn/problems/analyze-user-website-visit-pattern/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"joe\",\"joe\",\"joe\",\"james\",\"james\",\"james\",\"james\",\"mary\",\"mary\",\"mary\"]\\n[1,2,3,4,5,6,7,8,9,10]\\n[\"home\",\"about\",\"career\",\"home\",\"cart\",\"maps\",\"home\",\"home\",\"about\",\"career\"]', '[\"ua\",\"ua\",\"ua\",\"ub\",\"ub\",\"ub\"]\\n[1,2,3,4,5,6]\\n[\"a\",\"b\",\"a\",\"a\",\"b\",\"c\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:\n",
    "        def smaller(li1,li2):\n",
    "            for i in range(len(li1)):\n",
    "                if li1[i]<li2[i]:\n",
    "                    return True\n",
    "                elif li1[i]>li2[i]:\n",
    "                    return False\n",
    "            return False\n",
    "\n",
    "        user2data = defaultdict(list)\n",
    "        n = len(username)\n",
    "        for i in range(n):\n",
    "            user2data[username[i]].append((timestamp[i],website[i]))\n",
    "        for k in user2data.keys():\n",
    "            user2data[k].sort()\n",
    "        \n",
    "        pattern_cnt = defaultdict(int)\n",
    "        for v in user2data.values():\n",
    "            leng = len(v)\n",
    "            if leng<3:\n",
    "                continue\n",
    "            cnt = set()\n",
    "            visited1 = set()\n",
    "            for i in range(leng-2):\n",
    "                web1 = v[i][1]\n",
    "                if web1 in visited1:\n",
    "                    continue\n",
    "                visited1.add(web1)\n",
    "                visited2 = set()\n",
    "                for j in range(i+1,leng-1):\n",
    "                    web2 = v[j][1]\n",
    "                    if web2 in visited2:\n",
    "                        continue\n",
    "                    visited2.add(web2)\n",
    "                    visited3 = set()\n",
    "                    for k in range(j+1,leng):\n",
    "                        web3 = v[k][1]\n",
    "                        if web3 in visited3:\n",
    "                            continue\n",
    "                        visited3.add(web3)\n",
    "                        cnt.add((web1,web2,web3))\n",
    "            for pattern in cnt:\n",
    "                pattern_cnt[pattern]+=1\n",
    "        res = None\n",
    "        max_cnt = max(pattern_cnt.values())\n",
    "        for k,v in pattern_cnt.items():\n",
    "            if v==max_cnt:\n",
    "                if not res or smaller(k,res):\n",
    "                    res = list(k)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:\n",
    "\n",
    "        # split according to users:\n",
    "        pattern_group = []\n",
    "        pattern_group_dict = {}\n",
    "        for i in range(len(username)):\n",
    "            if username[i] not in pattern_group_dict:\n",
    "                pattern_group_dict[username[i]] = []\n",
    "            pattern_group_dict[username[i]].append([website[i], timestamp[i]])\n",
    "        for key in pattern_group_dict:\n",
    "            temp_pattern_with_time = pattern_group_dict[key]\n",
    "            temp_pattern_with_time.sort(key=lambda x: x[1])\n",
    "            temp_pattern = [x[0] for x in temp_pattern_with_time]\n",
    "            pattern_group.append(temp_pattern)\n",
    "        \n",
    "        # print(pattern_group)\n",
    "        pattern_map = collections.defaultdict(int)\n",
    "        for idx, group in enumerate(pattern_group):\n",
    "            added_set = set()\n",
    "            if len(group) < 3:\n",
    "                continue\n",
    "            for i in range(len(group)):\n",
    "                for j in range(i + 1, len(group)):\n",
    "                    for k in range(j + 1, len(group)):\n",
    "                        pattern = (group[i], group[j], group[k])\n",
    "                        if pattern not in added_set:\n",
    "                            pattern_map[pattern] += 1\n",
    "                            added_set.add(pattern)\n",
    "\n",
    "        # print(f\"pattern_map outsite: {pattern_map}\")\n",
    "        if len(pattern_map) > 0:\n",
    "            max_value = max(pattern_map.values())\n",
    "            patterns = [key for key, value in pattern_map.items() if value == max_value]\n",
    "            patterns.sort(key = lambda x: (x[0], x[1], x[2]))\n",
    "            return list(patterns[0])\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:\n",
    "        dct = defaultdict(list)\n",
    "        n = len(username)\n",
    "        for i in range(n):\n",
    "            dct[username[i]].append([timestamp[i], website[i]])\n",
    "        cnt = Counter()\n",
    "        for user in dct:\n",
    "            dct[user].sort()\n",
    "            lst = [ls[1] for ls in dct[user]]\n",
    "            cur = dict()\n",
    "            for order in combinations(lst, 3):\n",
    "                cur[tuple(order)] = 1\n",
    "            for x in cur:\n",
    "                cnt[x] += cur[x]\n",
    "        \n",
    "        ans = \"\"\n",
    "        res=  -1\n",
    "        for s in cnt:\n",
    "            if cnt[s] > res or (cnt[s] == res and s < ans):\n",
    "                ans = s\n",
    "                res = cnt[s]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, username: str, timestamp: int, website: str):\n",
    "        self.user = username\n",
    "        self.time = timestamp\n",
    "        self.web = website\n",
    "\n",
    "class Solution:\n",
    "    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:\n",
    "        n = len(username)\n",
    "        \n",
    "        \n",
    "        #----统计，按照时间排序\n",
    "        nodes = [None for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            nodes[i] = Node(username[i], timestamp[i], website[i])\n",
    "        nodes.sort(key = lambda x: x.time)\n",
    "\n",
    "        #----每个用户访问过的结点（已经是按时间排序了）\n",
    "        user_visit = collections.defaultdict(list)\n",
    "        for i in range(n): \n",
    "            x = nodes[i]\n",
    "            user_visit[x.user].append(x)\n",
    "\n",
    "        #----每个用户，自己访问过的路径，暴力构造长度为3的“路径”\n",
    "        path_freq = collections.defaultdict(int)\n",
    "        for user, visit in user_visit.items():\n",
    "            tmp_path_set = set()     #防止一个路径。用户重复访问！！！！（第一次就WA在这里了）\n",
    "            nn = len(visit)\n",
    "            for i in range(nn):\n",
    "                for j in range(i + 1, nn):\n",
    "                    for k in range(j + 1, nn):\n",
    "                        cur_path = visit[i].web + '#' + visit[j].web + '#' + visit[k].web \n",
    "                        tmp_path_set.add(cur_path)\n",
    "            \n",
    "            for path in tmp_path_set:\n",
    "                path_freq[path] += 1\n",
    "        # print(path_freq)\n",
    "\n",
    "        #----计算结果\n",
    "        max_freq = 0\n",
    "        res = \"\"\n",
    "        for path, f in path_freq.items():\n",
    "            if f > max_freq:\n",
    "                max_freq = f\n",
    "                res = path\n",
    "            elif f == max_freq:\n",
    "                rl = res.split('#')\n",
    "                pl = path.split('#')\n",
    "                if pl[0] < rl[0] or (pl[0] == rl[0] and pl[1] < rl[1]) or (pl[0] == rl[0] and pl[1] == rl[1] and pl[2] < rl[2]):\n",
    "                    res = path\n",
    "\n",
    "        return res.split('#')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:       \n",
    "        arr = list(zip(username, timestamp, website))\n",
    "        arr.sort()\n",
    "        l,r = 0,0\n",
    "        arr.append(('',0,''))\n",
    "        \n",
    "        cnt = defaultdict(set)\n",
    "        while r < len(arr):\n",
    "            if arr[r][0] == arr[l][0]:\n",
    "                r += 1\n",
    "            else:\n",
    "                for i in range(l,r-2):\n",
    "                    for j in range(i+1,r-1):\n",
    "                        for k in range(j+1,r):\n",
    "                            cnt[(arr[i][2],arr[j][2],arr[k][2])].add(arr[l][0])\n",
    "                l = r\n",
    "        \n",
    "        res = ()\n",
    "        tmp = 0\n",
    "        for key,val in cnt.items():\n",
    "            if len(val) > tmp:\n",
    "                tmp = len(val)\n",
    "                res = key\n",
    "            elif len(val) == tmp and key < res:\n",
    "                res = key\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param username:\n",
    "        :param timestamp:\n",
    "        :param website:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(list)\n",
    "        tt = [i for i in zip(username, timestamp, website)]\n",
    "        tt.sort(key=lambda x:x[1])\n",
    "        for i in tt:\n",
    "            m1[i[0]].append(i[2])\n",
    "\n",
    "        mm = defaultdict(int)\n",
    "        for i in m1:\n",
    "            s1 = set()\n",
    "            i = m1[i]\n",
    "            for a in range(len(i)):\n",
    "                for b in range(a+1, len(i)):\n",
    "                    for c in range(b+1, len(i)):\n",
    "                        s1.add((i[a], i[b], i[c]))\n",
    "            for x in s1:\n",
    "                mm[x] += 1\n",
    "        tt = [(i, mm[i]) for i in mm]\n",
    "        tt.sort(key=lambda x:(-x[1], x[0] ))\n",
    "        return tt[0][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:\n",
    "        n = len(username)\n",
    "        d = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            bisect.insort(d[username[i]],(timestamp[i],website[i]))\n",
    "        name = defaultdict(set)\n",
    "        for k,v in d.items():\n",
    "            for t in itertools.combinations([b for a,b in v],3):\n",
    "                name[t].add(k)\n",
    "        return sorted(name.items(),key = lambda x:(-len(x[1]),x[0]))[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 注意区分combinations和permutations的区别\n",
    "class Solution:\n",
    "    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:\n",
    "        n = len(username)\n",
    "        d = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            bisect.insort(d[username[i]],(timestamp[i],website[i]))\n",
    "        f = defaultdict(set)\n",
    "        for k,v in d.items():\n",
    "            for types in combinations([b for a,b in v],3):\n",
    "                f[types].add(k)\n",
    "        return sorted(f.items(),key = lambda x:(-len(x[1]),x[0]))[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostVisitedPattern(self, u: List[str], t: List[int], w: List[str]) -> List[str]:\n",
    "        n = len(u)\n",
    "        dic = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            bisect.insort(dic[u[i]], (t[i], w[i]))\n",
    "        name = collections.defaultdict(set)\n",
    "        for k, v in dic.items():\n",
    "            for t in itertools.combinations([b for a, b in v], 3):\n",
    "                name[t].add(k)\n",
    "        return sorted(name.items(), key = lambda x: (-len(x[1]), x[0]))[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:\n",
    "        n = len(username)\n",
    "        dic = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            bisect.insort(dic[username[i]], (timestamp[i], website[i]))\n",
    "        name = collections.defaultdict(set)\n",
    "        for k, v in dic.items():\n",
    "            for t in itertools.combinations([b for a, b in v], 3):\n",
    "                name[t].add(k)\n",
    "        \n",
    "        return sorted(name.items(), key=lambda x:(-len(x[1]), x[0]))[0][0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
